#链表

class LNode:
    '''链表节点'''
    def __init__(self, data):
        self.data = data #数据域
        self.next = None #下一个结点引用
    def __str__(self):
        lst = self
        data=[]
        while lst:
            data.append(lst.data)
            lst=lst.next
        return 'L:'+str(data)

n=LNode(3)
n.next=LNode(2)
n.next.next=LNode(6)
n.next.next.next=LNode(6)
n.next.next.next.next=LNode(2)
print(n)


#链表逆序

def Reverse(head):
    #判断链表是否为空
    if head == None or head.next == None: 
        return None
    pre = None #前驱结点
    cur = None #当前结点
    next = None #后继结点
    #把链表首结点变为尾结点
    cur = head.next
    next = cur.next
    cur.next = None
    pre = cur
    cur = next
    #使当前遍历到的结点cur 指向其前驱结点
    while cur.next != None:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = cur.next
        cur = next
    cur.next = pre #链表最后一个结点指向倒数第二个结点
    head.next = cur #链表的头结点指向原来链表的尾结点

def RecursiveReverse(head):
    # 如果链表为空或者链表中只有一个元素
    if head is None or head.next is None :
        return head
    else :
        # 反转后面的结点
        newhead=RecursiveReverse(head.next)
        # 把当前遍历的结点加到后面结点逆序后链表的尾部
        head.next.next=head
        head.next=None
    return newhead

def Reverse(head):
    if head is None:
        return None
    # 获取链表第一个结点并进行逆序
    firstNode=head.next
    newhead=RecursiveReverse(firstNode)
    # 头结点指向逆序后链表的第一个结点
    head.next=newhead
    return newhead

def Reverse(head):
    # 判断链表是否为空
    if head is None or head.next is None:
        return None
    cur = None #当前结点
    next = None #后继结点
    cur = head.next.next
    # 设置链表第一个结点为尾结点
    head.next.next = None
    # 把遍历到结点插入到头结点的后面
    while cur is not None:
        next = cur.next
        cur.next = head.next
        head.next = cur
        cur = next

# Reverse(n)
# print(n)

#删除无序链表的重复项

def removeDup(head):
    if head == None or head.next == None:
        return None
    outerCur = head.next # 用于外层循环，指向链表第一个结点
    innerCur = None # 用于内层循环用来遍历outerCur 后面的结点
    innerPre = None # innerCur 的前驱结点
    while outerCur != None:
        innerCur = outerCur.next
        innerPre = outerCur
        while innerCur != None:
            # 找到重复的结点并删除
            if outerCur.data == innerCur.data:
                innerPre.next = innerCur.next
                innerCur = innerCur.next
            else:
                innerPre = innerCur
                innerCur = innerCur.next
        outerCur = outerCur.next


def removeDupRecursion(head):
    if head.next is None:
        return head
    pointer = None
    cur = head
    #对以head.next 为首的子链表删除重复的结点
    head.next = removeDupRecursion(head.next)
    pointer = head.next
    # 找出以head.next 为首的子链表中与head 结点相同的结点并删除
    while pointer is not None:
        if head.data == pointer.data:
            cur.next = pointer.next
            pointer = cur.next
        else:
            pointer = pointer.next
            cur = cur.next
    return head

n=removeDupRecursion(n)
print(n)